//https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&tqId=23267&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

//美过()
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {

		ListNode* cur1 = pHead1;
		ListNode* cur2 = pHead2;



		int flag = 0;
		if(pHead1->val < pHead2->val)
		{
			flag = 0;
		}
		flag = 1;

        while(pHead1 || pHead2)
		{
			if(nullptr == pHead1)
			{
				return nullptr;
			}

			if(nullptr == pHead1)
			{

			}


			if(pHead1->val < pHead2->val)
			{
				ListNode* Next1 = pHead1->next;
				ListNode* Next2 = pHead2->next;
				pHead1->next = pHead2;
				if(Next1 == nullptr && pHead2->next != nullptr)
				{
					pHead2 = pHead2->next;
				}
				pHead1 = pHead1->next;
				pHead2 = pHead2->next;
			}
			else
			{
				pHead2->next = pHead1;
				ListNode* Next1 = pHead1->next;
				ListNode* Next2 = pHead2->next;
				if(Next2 == nullptr && pHead1->next != nullptr)
				{
					pHead1 = pHead1->next;
				}
				pHead2 = pHead2->next;
				pHead1 = pHead1->next;
			}

		}

		if(0 == flag)
		{
			return cur1;
		}
		return cur2;
    }
};


//抄的递归(过了)
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        //递归
		if(!pHead1)
		{
			return  pHead2;
		}
		if(!pHead2)
		{
			return pHead1;
		}

		if(pHead1->val < pHead2->val)
		{
			pHead1->next = Merge(pHead1->next,pHead2);
			return pHead1;
		}
		else 
		{
			pHead2->next = Merge(pHead2->next, pHead1);
			return pHead2;
		}
    }
};
